package main

import (
	"fmt"
)

type Node struct {
	data interface{}
	next *Node
}

type singleLinked struct {
	head *Node
}

func (this *singleLinked) Empty() bool {
	if this.head == nil{
		return true
	}else {
		return false
	}
}

func (this *singleLinked) Length() int {
	cur := this.head  // 获取头结点游标
	count := 0
	for {
		if cur != nil {
			count ++
			cur = cur.next
		}else {
			break
		}

	}
	return count
}

func (this *singleLinked) Add(param interface{})  {
	// 链表头部插入
	node := &Node{data: param}
	//temp := this.head
	//node.next = temp
	//this.head = node
	node.next, this.head = this.head, node
}

func (this *singleLinked) Append(param interface{})  {
	// 链表尾部插入
	node := &Node{data: param}
	if this.Empty(){
		this.head = node
	}else {
		cur := this.head
		for {
			if cur.next != nil{
				cur = cur.next
			}else {
				cur.next = node
				break
			}
		}

	}
}

func (this *singleLinked) Insert(param interface{}, pos int) {
	// 指定位置插入
	if pos <= 0 {
		this.Add(param)
	}else if pos >= this.Length(){
		this.Append(param)
	}else {
		node := &Node{data: param}
		count := 0  // 标记位置
		pre := this.head  // 指向指定位置pos的前一个位置，即pos-1
		for count < (pos -1) {
				count++
				pre = pre.next
		}
		// 退出循环表示找到位置
		node.next = pre.next
		pre.next = node
	}
}

func (this *singleLinked) Remove(param interface{})  {
	// 删除指定元素
	cur := this.head
	if cur.data == param {
		// 删除头结点
		this.head = cur.next
	}
	for cur.next != nil{
		if cur.next.data != param{
			cur = cur.next
		}else {
			cur.next = cur.next.next
		}
	}
}

func (this *singleLinked) RemoveWithIndex(index int) {
	// 删除指定索引的数据
	cur := this.head
	if index <= 0{
		this.head = cur.next
	}else if index >this.Length(){
		fmt.Println("超出链表长度")
		return
	}else {
		count := 0  // 标记位置
		//pre := this.head  // 指向指定位置pos的前一个位置，即pos-1
		for count < (index -1) {
			count++
			cur = cur.next
		}
		// 退出循环表示找到位置
		cur.next = cur.next.next
	}
}

func (this *singleLinked) Travel() {
	if !this.Empty() {
		cur := this.head
		for {
			if cur != nil{
				fmt.Printf("%v  ", cur.data)
				cur = cur.next
				// 这两行代码不能换位置，否则panic
			}else {
				break
			}
		}
	}
}

func (this *singleLinked) Find(param interface{}) bool {
	cur := this.head
	for cur.next != nil{
		if cur.data == param{
			return true
		}else {
			cur = cur.next
		}
	}
	return false
}


func main() {
	singleLinked := singleLinked{}
	singleLinked.Add(15)
	singleLinked.Add("go")
	singleLinked.Add(20)
	singleLinked.Travel()
	fmt.Println()
	singleLinked.Append(3.2)
	singleLinked.Append("append")
	singleLinked.Travel()
	fmt.Println()
	singleLinked.Insert("insert1", 1)
	singleLinked.Travel()
	fmt.Println()
	singleLinked.Insert("insert2", 2)
	singleLinked.Travel()
	fmt.Println()
	//singleLinked.Remove(20)
	singleLinked.Remove("go")
	singleLinked.Travel()
	fmt.Println()
	singleLinked.RemoveWithIndex(3)
	singleLinked.Travel()
	fmt.Println()
	singleLinked.Insert("再次insert", 2)
	singleLinked.Travel()
	fmt.Println()
	res := singleLinked.Find("insert")
	res1 := singleLinked.Find("haha")
	fmt.Println(res, res1)
	length := singleLinked.Length()
	fmt.Println(length)

}